package leetcode.D200.T148;

import util.ListNode;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    /*// 解法一：归并（递归方式），时间O(nlogn)，空间O(logn)
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode slow = head, fast = head.next;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        fast = slow.next;
        slow.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(fast);
        ListNode newHead = new ListNode(0);
        ListNode t = newHead;
        while(left != null && right != null) {
            if(left.val <= right.val) {
                t.next = left;
                left = left.next;
            } else {
                t.next = right;
                right = right.next;
            }
            t = t.next;
        }
        t.next = left == null ? right : left;
        return newHead.next;
    }*/
    // 解法二：归并（非递归方式），时间O(nlogn)，空间O(1)
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        int length = 0;
        ListNode p = head;
        while(p != null) {
            length++;
            p = p.next;
        }
        int intv = 1, step = 0;
        ListNode newHead = new ListNode(0);
        ListNode t = newHead;
        ListNode left = head, right = null;
        while(intv < length) {
            int nextLoc = step * 2 * intv + intv;
            if(nextLoc < length) { // 有右半边，但可能不全
                right = left;
                for(int i=0; i<intv; ++i) {
                    right = right.next;
                }
            } else {
                while(left != null) {
                    t.next = left;
                    left = left.next;
                    t = t.next;
                }
                t.next = null;
                t = newHead;
                left = newHead.next;
                intv *= 2;
                step = 0;
                continue;
            }
            int leftLen = intv, rightLen = Math.min(length - nextLoc, intv), i = 0, j = 0;
            while(i < leftLen && j < rightLen) {
                if(left.val <= right.val) {
                    t.next = left;
                    left = left.next;
                    ++i;
                } else {
                    t.next = right;
                    right = right.next;
                    ++j;
                }
                t = t.next;
            }
            while(i < leftLen) {
                t.next = left;
                left = left.next;
                ++i;
                t = t.next;
            }
            while(j < rightLen) {
                t.next = right;
                right = right.next;
                ++j;
                t = t.next;
            }
            step++;
            left = right;
            if(right == null) {
                left = newHead.next;
                t.next = null;
                t = newHead;
                intv *= 2;
                step = 0;
            }
        }
        return newHead.next;
    }
    // 解法三：快排
}